package leetCode.offer07;


/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 * 示例 1:
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 * 示例 2:
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *
 * 限制：
 * 0 <= 节点个数 <= 5000
 */
public class Solution2 implements Solution{


    static int preIndex = 0;

    /**
     * 递归优化版解答
     * @param preorder
     * @param inorder
     * @return
     */
    @Override
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preIndex = 0;
        return buildBinaryTree(preorder,inorder,0,inorder.length);
    }

    /**
     * 根据前序，中序遍历数组重建树
     * @param preOrder
     * @param inOrder
     * @param inStart
     * @param inEnd
     * @return
     */
   static TreeNode buildBinaryTree(int[] preOrder, int[] inOrder, int inStart, int inEnd) {
        if(inStart > inEnd) return null;
        if(preIndex < preOrder.length) {
            TreeNode root = new TreeNode(preOrder[preIndex]);
            if(inStart == inEnd) {
                return root;
            }
            int inIndex = -1;
            for(int i = inStart ;i < inEnd;i++){
                if(inOrder[i] == root.val){
                    inIndex = i;
                }
            }
            root.left = buildBinaryTree(preOrder,inOrder,inStart,inIndex);
            root.right = buildBinaryTree(preOrder,inOrder,inIndex+1,inEnd);
            return root;
        }
        return null;
    }

    public static void main(String[] args) {
        int[] preorder = {1,2,3};
        int[] inorder = {3,2,1};
        System.out.println(new Solution2().buildTree(preorder,inorder).val);
    }

}
